package features.advance.leetcode.array.easy;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author LIN
 * @date 2022-01-07 16:25
 *
 *  217. 存在重复元素
 *
 *  难度：简单
 *
 * 给定一个整数数组，判断是否存在重复元素。
 *
 * 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [1,2,3,1]
 * 输出: true
 * 示例 2:
 *
 * 输入: [1,2,3,4]
 * 输出: false
 * 示例 3:
 *
 * 输入: [1,1,1,3,3,4,3,2,4,2]
 * 输出: true
 *
 */
public class Solution217 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            // 自己写hash表
            public boolean containsDuplicate(int[] nums) {
                int n = nums.length ;
                if (n < 2){
                    return false ;
                }

                // 创建哈希表
                int[] hash = new int[n] ;
                int zero = 0 ;

                for (int i = 0 ; i < n ; i++){
                    hash[i] = 0 ;
                }

                for (int i = 0 ; i < n ; i++){
                    if (nums[i] == 0){
                        zero++ ;
                        if (zero > 1){
                            return true ;
                        }
                        continue;
                    }

                    int remainder = nums[i] % n ;
                    if (remainder < 0){
                        remainder += n ;
                    }

                    while (true){
                        if (hash[remainder] == 0){
                            hash[remainder] = nums[i] ;
                            break;
                        }else if (hash[remainder] == nums[i]){
                            return true ;
                        }else {
                            remainder++ ;
                            if (remainder >= n){
                                remainder -= n ;
                            }
                        }
                    }
                }
                return false ;
            }
        };

        int[][] test = {
                {1,2,3,1},
                {1,2,3,4},
                {1,1,1,3,3,4,3,2,4,2}
        };
        for (int[] nums : test) {
            boolean containsDuplicate = solution.containsDuplicate(nums);
            System.out.println("Inputs:"+ Arrays.toString(nums)+"  Outputs:"+containsDuplicate);
        }
    }

    static class Solution {
        public boolean containsDuplicate(int[] nums) {
            if(nums == null || nums.length == 0){
                return false;
            }
            Set<Integer> set = new HashSet(16);
            for(int i=0;i<nums.length;i++){
                int o = nums[i];
                if(set.contains(o)){
                    return true;
                }else{
                    set.add(o);
                }

            }
            return false;
        }
    }
}
